package blue_bridge_cup_learning.差分;

import java.util.Arrays;

// 一个数组 a 中共包含 n 个数，问最少多少次操作，可以让 a 数组所有数都变成 1。
// 操作的内容是：每次操作可以任选一个区间使得区间内的所有数字减 1。数据保证一定有解。
public class 小蓝的操作 {
    public static void main(String[] args) {
        int[] arr = { 1, 3, 5, 2, 7, 1 };
        int[] arr_copy = new int[arr.length + 1];
        for (int i = 1; i < arr_copy.length; i++) {
            arr_copy[i] = arr[i - 1];
        }
        int[] diff_arr = new int[arr.length + 1];
        // 构建差分数组
        for (int i = 1; i < arr.length + 1; i++) {
            diff_arr[i] = arr_copy[i] - arr_copy[i - 1];
        }
        System.out.println(Arrays.toString(diff_arr));
        // 只需要正数的值大于复数即可
        int res = 0;
        for (int i = 1; i < diff_arr.length; i++) {
            if (diff_arr[i] > 0) {
                res += diff_arr[i];
            }
        }
        System.out.println(res - 1);
    }
}
